home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_419 / yacc / src.lzh / Src / mkpar.c < prev    next >
C/C++ Source or Header  |  1990-07-14  |  7KB  |  372 lines
  1. #include "defs.h"
  2.  
  3. action **parser;
  4. int SRtotal;
  5. int RRtotal;
  6. short *SRconflicts;
  7. short *RRconflicts;
  8. short *defred;
  9. short *rules_used;
  10. short nunused;
  11. short final_state;
  12.  
  13. static int SRcount;
  14. static int RRcount;
  15.  
  16. extern action *parse_actions();
  17. extern action *get_shifts();
  18. extern action *add_reductions();
  19. extern action *add_reduce();
  20.  
  21.  
  22. make_parser()
  23. {
  24.     register int i;
  25.  
  26.     parser = NEW2(nstates, action *);
  27.     for (i = 0; i < nstates; i++)
  28.     parser[i] = parse_actions(i);
  29.  
  30.     find_final_state();
  31.     remove_conflicts();
  32.     unused_rules();
  33.     if (SRtotal + RRtotal > 0) total_conflicts();
  34.     defreds();
  35. }
  36.  
  37.  
  38. action *
  39. parse_actions(stateno)
  40. register int stateno;
  41. {
  42.     register action *actions;
  43.  
  44.     actions = get_shifts(stateno);
  45.     actions = add_reductions(stateno, actions);
  46.     return (actions);
  47. }
  48.  
  49.  
  50. action *
  51. get_shifts(stateno)
  52. int stateno;
  53. {
  54.     register action *actions, *temp;
  55.     register shifts *sp;
  56.     register short *to_state;
  57.     register int i, k;
  58.     register int symbol;
  59.  
  60.     actions = 0;
  61.     sp = shift_table[stateno];
  62.     if (sp)
  63.     {
  64.     to_state = sp->shift;
  65.     for (i = sp->nshifts - 1; i >= 0; i--)
  66.     {
  67.         k = to_state[i];
  68.         symbol = accessing_symbol[k];
  69.         if (ISTOKEN(symbol))
  70.         {
  71.         temp = NEW(action);
  72.         temp->next = actions;
  73.         temp->symbol = symbol;
  74.         temp->number = k;
  75.         temp->prec = symbol_prec[symbol];
  76.         temp->action_code = SHIFT;
  77.         temp->assoc = symbol_assoc[symbol];
  78.         actions = temp;
  79.         }
  80.     }
  81.     }
  82.     return (actions);
  83. }
  84.  
  85. action *
  86. add_reductions(stateno, actions)
  87. int stateno;
  88. register action *actions;
  89. {
  90.     register int i, j, m, n;
  91.     register int ruleno, tokensetsize;
  92.     register unsigned *rowp;
  93.  
  94.     tokensetsize = WORDSIZE(ntokens);
  95.     m = lookaheads[stateno];
  96.     n = lookaheads[stateno + 1];
  97.     for (i = m; i < n; i++)
  98.     {
  99.     ruleno = LAruleno[i];
  100.     rowp = LA + i * tokensetsize;
  101.     for (j = ntokens - 1; j >= 0; j--)
  102.     {
  103.         if (BIT(rowp, j))
  104.         actions = add_reduce(actions, ruleno, j);
  105.     }
  106.     }
  107.     return (actions);
  108. }
  109.  
  110.  
  111. action *
  112. add_reduce(actions, ruleno, symbol)
  113. register action *actions;
  114. register int ruleno, symbol;
  115. {
  116.     register action *temp, *prev, *next;
  117.  
  118.     prev = 0;
  119.     for (next = actions; next && next->symbol < symbol; next = next->next)
  120.     prev = next;
  121.  
  122.     while (next && next->symbol == symbol && next->action_code == SHIFT)
  123.     {
  124.     prev = next;
  125.     next = next->next;
  126.     }
  127.  
  128.     while (next && next->symbol == symbol &&
  129.         next->action_code == REDUCE && next->number < ruleno)
  130.     {
  131.     prev = next;
  132.     next = next->next;
  133.     }
  134.  
  135.     temp = NEW(action);
  136.     temp->next = next;
  137.     temp->symbol = symbol;
  138.     temp->number = ruleno;
  139.     temp->prec = rprec[ruleno];
  140.     temp->action_code = REDUCE;
  141.     temp->assoc = rassoc[ruleno];
  142.  
  143.     if (prev)
  144.     prev->next = temp;
  145.     else
  146.     actions = temp;
  147.  
  148.     return (actions);
  149. }
  150.  
  151.  
  152. find_final_state()
  153. {
  154.     register int goal, i;
  155.     register short *to_state;
  156.     register shifts *p;
  157.  
  158.     p = shift_table[0];
  159.     to_state = p->shift;
  160.     goal = ritem[1];
  161.     for (i = p->nshifts - 1; i >= 0; --i)
  162.     {
  163.     final_state = to_state[i];
  164.     if (accessing_symbol[final_state] == goal) break;
  165.     }
  166. }
  167.  
  168.  
  169. unused_rules()
  170. {
  171.     register int i;
  172.     register action *p;
  173.  
  174.     rules_used = (short *) MALLOC(nrules*sizeof(short));
  175.     if (rules_used == 0) no_space();
  176.  
  177.     for (i = 0; i < nrules; ++i)
  178.     rules_used[i] = 0;
  179.  
  180.     for (i = 0; i < nstates; ++i)
  181.     {
  182.     for (p = parser[i]; p; p = p->next)
  183.     {
  184.         if (p->action_code == REDUCE && p->suppressed == 0)
  185.         rules_used[p->number] = 1;
  186.     }
  187.     }
  188.  
  189.     nunused = 0;
  190.     for (i = 3; i < nrules; ++i)
  191.     if (!rules_used[i]) ++nunused;
  192.  
  193.     if (nunused)
  194.     if (nunused == 1)
  195.         fprintf(stderr, "%s: 1 rule never reduced\n", myname);
  196.     else
  197.         fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
  198. }
  199.  
  200.  
  201. remove_conflicts()
  202. {
  203.     register int i;
  204.     register int symbol;
  205.     register action *p, *q;
  206.  
  207.     SRtotal = 0;
  208.     RRtotal = 0;
  209.     SRconflicts = NEW2(nstates, short);
  210.     RRconflicts = NEW2(nstates, short);
  211.     for (i = 0; i < nstates; i++)
  212.     {
  213.     SRcount = 0;
  214.     RRcount = 0;
  215.     for (p = parser[i]; p; p = q->next)
  216.     {
  217.         symbol = p->symbol;
  218.         q = p;
  219.         while (q->next && q->next->symbol == symbol)
  220.         q = q->next;
  221.         if (i == final_state && symbol == 0)
  222.         end_conflicts(p, q);
  223.         else if (p != q)
  224.         resolve_conflicts(p, q);
  225.     }
  226.     SRtotal += SRcount;
  227.     RRtotal += RRcount;
  228.     SRconflicts[i] = SRcount;
  229.     RRconflicts[i] = RRcount;
  230.     }
  231. }
  232.  
  233.  
  234. end_conflicts(p, q)
  235. register action *p, *q;
  236. {
  237.     for (;;)
  238.     {
  239.     SRcount++;
  240.     p->suppressed = 1;
  241.     if (p == q) break;
  242.     p = p->next;
  243.     }
  244. }
  245.  
  246.  
  247. resolve_conflicts(first, last)
  248. register action *first, *last;
  249. {
  250.     register action *p;
  251.     register int count;
  252.  
  253.     count = 1;
  254.     for (p = first; p != last; p = p->next)
  255.      ++count;
  256.     assert(count > 1);
  257.  
  258.     if (first->action_code == SHIFT && count == 2 &&
  259.         first->prec > 0 && last->prec > 0)
  260.     {
  261.     if (first->prec == last->prec)
  262.     {
  263.         if (first->assoc == LEFT)
  264.         first->suppressed = 2;
  265.         else if (first->assoc == RIGHT)
  266.         last->suppressed = 2;
  267.         else
  268.         {
  269.         first->suppressed = 2;
  270.         last->suppressed = 2;
  271.         first->action_code = ERROR;
  272.         last->action_code = ERROR;
  273.         }
  274.     }
  275.     else if (first->prec < last->prec)
  276.         first->suppressed = 2;
  277.     else
  278.         last->suppressed = 2;
  279.     }
  280.     else
  281.     {
  282.     if (first->action_code == SHIFT)
  283.         SRcount += (count - 1);
  284.         else
  285.         RRcount += (count - 1);
  286.     for (p = first; p != last; p = p->next, p->suppressed = 1)
  287.         continue;
  288.     }
  289. }
  290.  
  291.  
  292. total_conflicts()
  293. {
  294.     fprintf(stderr, "%s: ", myname);
  295.     if (SRtotal == 1)
  296.     fprintf(stderr, "1 shift/reduce conflict");
  297.     else if (SRtotal > 1)
  298.     fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  299.  
  300.     if (SRtotal && RRtotal)
  301.     fprintf(stderr, ", ");
  302.  
  303.     if (RRtotal == 1)
  304.     fprintf(stderr, "1 reduce/reduce conflict");
  305.     else if (RRtotal > 1)
  306.     fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  307.  
  308.     fprintf(stderr, ".\n");
  309. }
  310.  
  311.  
  312. int
  313. sole_reduction(stateno)
  314. int stateno;
  315. {
  316.     register int count, ruleno;
  317.     register action *p;
  318.  
  319.     count = 0;
  320.     ruleno = 0; 
  321.     for (p = parser[stateno]; p; p = p->next)
  322.     {
  323.     if (p->action_code == SHIFT && p->suppressed == 0)
  324.         return (0);
  325.     else if (p->action_code == REDUCE && p->suppressed == 0)
  326.     {
  327.         if (ruleno > 0 && p->number != ruleno)
  328.         return (0);
  329.         if (p->symbol != 1)
  330.         ++count;
  331.         ruleno = p->number;
  332.     }
  333.     }
  334.  
  335.     if (count == 0)
  336.     return (0);
  337.     return (ruleno);
  338. }
  339.  
  340.  
  341. defreds()
  342. {
  343.     register int i;
  344.  
  345.     defred = NEW2(nstates, short);
  346.     for (i = 0; i < nstates; i++)
  347.     defred[i] = sole_reduction(i);
  348. }
  349.  
  350. free_action_row(p)
  351. register action *p;
  352. {
  353.   register action *q;
  354.  
  355.   while (p)
  356.     {
  357.       q = p->next;
  358.       FREE(p);
  359.       p = q;
  360.     }
  361. }
  362.  
  363. free_parser()
  364. {
  365.   register int i;
  366.  
  367.   for (i = 0; i < nstates; i++)
  368.     free_action_row(parser[i]);
  369.  
  370.   FREE(parser);
  371. }
  372.